package sort;

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

/**
 * @author dx
 * @version 1.0
 * @date 2022/3/25 11:24
 * @description:
 * 给定一个非空数组，返回此数组中第三大的数，如果不存在，则返回数组中最大的数
 */
public class Third_Num {


    public static int findMax(int[] nums){

        int firstMax = nums[0];
        for(int num : nums){
            if(num > firstMax){
                firstMax = num;
            }
        }
        return firstMax;

    }

    public static int thirdMax(int[] nums){

        int firstMax = findMax(nums);
        Set<Integer> set = new HashSet<Integer>();  //定义一个set : 保存一个去除原数组中最大值的集合
        Set<Integer> set2 = new HashSet<Integer>();
        Set<Integer> set3 = new HashSet<Integer>();
        for(int num:nums) {
            if (num != firstMax) {
                set.add(num);
            }
        }
        if(set.size() == 0){
            return firstMax;
        }
            int second[] = new int[set.size()];
             int index = 0;
            for(int num : set){
                second[index++] = num;
            }
            int secondMax = findMax(second);
            for(int num: second){
                if(num != secondMax){
                    set2.add(num);
                }
            }
            if(set2.size()==0){
                return firstMax;
            }
        int third[] = new int[set2.size()];
        int index2 = 0;
        for(int num :set2){
            third[index2++] = num;
        }
        return findMax(third);

    }


    //方法2：Treset
    public static int thirddMax2(int[] nums){
        TreeSet<Integer> s = new TreeSet<>();
        for(int num : nums){
            s.add(num);
            if(s.size()>3){
                s.remove(s.first());
            }
        }
        return s.size() == 3 ? s.first():s.last();
    }
}
